【LeetCode 31】Next Permutation 下一个排列

发表于 | 分类于


“The Linux philosophy is “Laugh in the face of danger”.Oops.Wrong One. “Do it yourself”. Yes, that”s it.”
Linux的哲学就是“在危险面前放声大笑”，呵呵，不是这句，应该是“一切靠自己，自力更生”才对。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * 根据一棵树的前序遍历与中序遍历构造二叉树
 * 注意:
 * 你可以假设树中没有重复的元素。
 *
 * 递归构建
 */

public class leetcode105 {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    //根据前序和中序构件树
    public TreeNode buildTree (int[] preorder, int[] inorder) {
        return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode helper (int[] preorder, int preS, int preE, int[] inorder, int inS, int inE) {
        if (preS > preE || inS > inE)
            return null;
        TreeNode res = new TreeNode(preorder[preS]);
        int pos = inS;
        for (int i = inS; i <= inE; i++) {
            if (inorder[i] == preorder[preS]) {
                pos = i;
                break;
            }
        }
        //这个preE要算准确
        res.left = helper(preorder, preS + 1, preS + pos-inS, inorder, inS, pos - 1);
        res.right = helper(preorder, preS + pos-inS+1, preE, inorder, pos + 1, inE);
        return res;
    }

}
Thanks!